package com.zs.letcode.illustration_of_algorithm;

import java.util.*;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 * <p>
 * 限制：
 * <p>
 * 0 <= 链表长度 <= 10000
 * <p>
 * 相关标签
 * 栈
 * 递归
 * 链表
 * 双指针
 * <p>
 * Python3
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dt66m/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/8 11:25
 */
public class Chapter2 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(2);

        node1.next = node2;
        node2.next = node3;
    }

    /**
     * Definition for singly-linked list.
     */
    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    private static class Solution {
        /**
         * 方法一：栈
         *
         * @param head
         * @return
         */
        public int[] reversePrint(ListNode head) {
            Deque<ListNode> stack = new LinkedList();
            ListNode temp = head;
            while (Objects.nonNull(temp)) {
                stack.push(temp);
                temp = temp.next;
            }
            int size = stack.size();
            int[] print = new int[size];
            for (int i = 0; i < size; i++) {
                print[i] = stack.pop().val;
            }
            return print;
        }

        /**
         * 方法一：递归法
         */
        List<Integer> tmp = new ArrayList<>();

        public int[] reversePrint1(ListNode head) {
            recur(head);
            int[] res = new int[tmp.size()];
            for (int i = 0; i < res.length; i++) {
                res[i] = tmp.get(i);
            }
            return res;
        }

        private void recur(ListNode head) {
            if (head == null) return;
            recur(head.next);
            tmp.add(head.val);
        }
    }
}
